'''
主要分为三步：
1. 找到中点
2. 链表反转
3. 合并链表（各一位插一个）

'''
def reorderList(self, head: ListNode) -> None:
    if not head:
        return None

    def findMid(node):
        slow = fast = node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse(node):
        pre, cur = None, node
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
            # cur.next, pre, cur = pre, cur, cur.next
        return pre

    def merge(node1, node2):
        # node1在前node2在后
        # 也可以写while node1.next or node2.next
        while node1 and node2:
            tmp1, tmp2 = node1.next, node2.next
            # node1指向node2
            node1.next = node2
            # node1往后走一位
            node1 = tmp1
            # node2指向移位后的node1
            node2.next = node1
            # node2往后走一位
            node2 = tmp2

    mid = findMid(head)
    left, right = head, mid.next
    # break the list or there will be cycle
    # left和right变成两个链
    mid.next = None

    right = reverse(right)
    merge(left, right)